import java.util.*;

public class Main {

    //
//    public ListNode swapPairs(ListNode head) {
//        if(head == null || head.next == null) { return head;}
//
//        ListNode tmp = swapPairs(head.next.next);
//        ListNode ret = head.next;
//        ret.next = head;
//        head.next = tmp;
//
//        return ret;
//    }

    //
    public double myPow(double x, int n) {
        return n < 0 ? 1.0 / pow(x , -n) : pow(x, n);
    }

    public double pow(double x, int n){
        if(n == 0) { return 1.0;}

        double tmp = pow(x, n / 2);
        return n % 2 == 0 ? tmp * tmp : tmp * tmp * x;
    }

    //
//    public boolean evaluateTree(TreeNode root) {
//        if(root.left == null) {return root.val == 0 ? false : true;}
//
//        boolean left = evaluateTree(root.left);
//        boolean right = evaluateTree(root.right);
//
//        return root.val == 2 ? left | right : left & right;
//    }

    //
//    public int sumNumbers(TreeNode root) {
//        return dfs(root, 0);
//    }
//
//    public int dfs(TreeNode root, int prev){
//        prev = prev * 10 + root.val;
//        if(root.left == null && root.right == null){
//            return prev;
//        }
//
//        int ret = 0;
//        if(root.left != null) { ret += dfs(root.left, prev);}
//        if(root.right != null) { ret += dfs(root.right, prev);}
//        return ret;
//    }

    //
//    public TreeNode pruneTree(TreeNode root) {
//        if(root == null) { return null;}
//
//        root.left = pruneTree(root.left);
//        root.right = pruneTree(root.right);
//        if(root.left == null && root.right == null && root.val == 0){
//            root = null;
//        }
//        return root;
//    }

    //
//    long prev = Long.MIN_VALUE;
//    public boolean isValidBST(TreeNode root) {
//        if(root == null) {return true;}
//
//        boolean left = isValidBST(root.left);
//        boolean cur = false;
//        if(root.val > prev) { cur = true;}
//
//        prev = root.val;
//        boolean right = isValidBST(root.right);
//        return left && right && cur;
//    }

//    long prev = Long.MIN_VALUE;
//    public boolean isValidBST(TreeNode root) {
//        if(root == null) {return true;}
//
//        boolean left = isValidBST(root.left);
//        if(left == false) { return false;}
//        boolean cur = false;
//        if(root.val > prev) { cur = true;}
//        if(cur == false) { return false;}
//
//        prev = root.val;
//        boolean right = isValidBST(root.right);
//        return left && right && cur;
//    }
}
